package leetcode_2601_2700;

import java.util.*;
import java.util.List;

public class LeeCode_2608_failed {
    public static void main(String[] args) {
//        System.out.println(findShortestCycle(7, new int[][]{{0, 1},
//                {1, 2}, {2, 0}, {3, 4}, {4, 5}, {5, 6}, {6, 3}}));
//        System.out.println(findShortestCycle(4, new int[][]{{0, 1}, {0, 2}}));
        System.out.println(findShortestCycle(5, new int[][]{{0, 2}, {2, 4}, {4, 0}}));
    }

    private static int findShortestCycle(int n, int[][] edges) {
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int[] edge : edges) {
            int p1 = edge[0];
            int p2 = edge[1];
            if (map.containsKey(p1)) {
                map.get(p1).add(p2);
            } else {
                List<Integer> list = new ArrayList<>();
                list.add(p2);
                map.put(p1, list);
            }
            if (map.containsKey(p2)) {
                map.get(p2).add(p1);
            } else {
                List<Integer> list = new ArrayList<>();
                list.add(p1);
                map.put(p2, list);
            }
        /*    if (map.containsKey(p1) && !map.containsKey(p2)){
                List<Integer> list = new ArrayList<>();
                list.add(p1);
                map.put(p2, list);
            }else if (map.containsKey(p2) && !map.containsKey(p1)){
                List<Integer> list = new ArrayList<>();
                list.add(p2);
                map.put(p1, list);
            }else {
                List<Integer> list = new ArrayList<>();
                list.add(p2);
                map.put(p1, list);
            }*/
        }
        int[] min = new int[1];
        min[0] = Integer.MAX_VALUE;
        Set<String> used = new HashSet<>();
        for (int i = 0; i < n; i++) {
            bfs(map, min, i, i, used, 1);
        }
        return min[0] == Integer.MAX_VALUE ? -1 : min[0];
    }

    private static void bfs(Map<Integer, List<Integer>> map, int[] min, int point, int start, Set<String> used, int count) {
        if (used.contains("" + start + "," + point))
            return;
        used.add("" + start + "," + point);
        List<Integer> list = map.get(point);
        if (list == null)
            return;
        for (Integer next : list) {
            if (next == start) {
                if (count < 3)
                    continue;
                min[0] = Math.min(min[0], count);
                return;
            }
            bfs(map, min, next, start, used, count + 1);
        }
    }
}
